package chart.shortest_path;

import chart.图的存储.AbstractGraph;
import chart.图的存储.AdjacencyMatrix;
import chart.图的存储.AdjacencyTable;
import chart.图的存储.Edge;

import java.lang.annotation.Target;
import java.util.*;

/**
 * 迪杰斯特拉算法
 * <p>只有当权值为正的时候用，权值为负的要使用贝尔曼-福德算法</p>
 * <p>类似 prime 算法, 针对顶点, 每次把距离最小的顶点加入到路径中</p>
 * <p>贪心</p>
 * <p>算法要点：</p>
 * <p>distance[]：存储顶点到该点的距离, 达不到就设置为 Integer.MAX_VALUE</p>
 * <p>path[]：顶点到该点的前驱顶点</p>
 * <p>visited[]；判断当前顶点是否已经走过, 防止图有环从而导致死循环</p>
 *
 * <p>时间复杂度：O(V * V)</p>
 * 每次找出最短的路线
 * 需要四个存储
 * 1、图 , 由自定义节点组成 , 节点有 String 和 Map , 还是用 Map<String, Node> 方便找到节点
 * 2、节点的开销 , 指的是从起点出发前往该节点所需的时间 , 使用 map 存储 , key 为节点 , value 为起点到达这个节点的最小路径
 * 3、到达这个节点的前一个节点，即这个节点的父节点 , 使用 map 存储 ,
 * Map<String, String> , key -> 节点，因为节点不能重复 , value -> 节点的父节点
 * 4、已经遍历过的节点 , 使用 set 存储 , 防止重复
 * 找最小边，看到的那个节点有没有遍历过，比如 a -> b 为最小边时，要看 b 节点有没有被遍历过
 * 思路：
 * 结束条件：alreadFind 的长度等于 chart 的长度 -1
 * 每次找到最小长度对应的那个节点时，要改变 minPath 中的值
 * 找到要遍历的节点时，比较该节点到连接节点的大小与连接节点的值的大小，如果比原来的小，则更新
 *
 * @author yzh
 * @version 1.0
 * @date 2021/4/13 9:27
 */
public class Dijkstra {
    public static void main(String[] args) {
        testAdjacencyMatrix();
    }

    private static void testAdjacencyMatrix() {
        AbstractGraph graph = new AdjacencyMatrix(6, false);
        graph.createGraph(Edge.graphDFS());
        getMinDis(0, graph);
        dijkstra(graph, 0);
    }

    private static void testAdjacencyTable() {
        AbstractGraph graph = new AdjacencyTable(6, false);
        graph.createGraph(Edge.graphDFS());
        getMinDis(0, graph);
    }

    private void test() {
        Dijkstra dijkstra = new Dijkstra();

        Map<String, Node> chart = new LinkedHashMap<>();
        dijkstra.createChart(chart);

        Map<String, Integer> minPath = new HashMap<>();
        Map<String, String> parentNode = new HashMap<>();
        Set<String> alreadyFind = new HashSet<>();
        dijkstra.createMinPath("A", minPath, alreadyFind, parentNode, chart);
        System.out.println(dijkstra.getMin(chart, alreadyFind, minPath, parentNode, "E"));
        System.out.println(minPath);
        System.out.println(parentNode);
    }

    public void createNode(String parent, List<String> keys, List<Integer> values, Map<String, Node> chart) {
        chart.put(parent, new Node(parent, keys, values));
        keys.clear();
        values.clear();
    }

    public void createChart(Map<String, Node> chart) {
        List<String> keys = new ArrayList<>();
        List<Integer> values = new ArrayList<>();
//        keys.add("B"); keys.add("C"); values.add(5); values.add(2);
//        createNode("A", keys, values, chart);
//
//        keys.add("D"); keys.add("E"); values.add(4); values.add(2);
//        createNode("B", keys, values, chart);
//
//        keys.add("B"); keys.add("E"); values.add(8); values.add(7);
//        createNode("C", keys, values, chart);
//
//        keys.add("E"); keys.add("F"); values.add(6); values.add(3);
//        createNode("D", keys, values, chart);
//
//        keys.add("F"); values.add(1);
//        createNode("E", keys, values, chart);
//
//        chart.put("F", new Node("F", null, null));

        keys.add("B");
        values.add(10);
        createNode("A", keys, values, chart);

        keys.add("C");
        values.add(20);
        createNode("B", keys, values, chart);

        keys.add("D");
        keys.add("E");
        values.add(1);
        values.add(30);
        createNode("C", keys, values, chart);

        keys.add("B");
        values.add(1);
        createNode("D", keys, values, chart);

        chart.put("E", new Node("E", null, null));
    }

    /**
     * 创建最小路径的时候，相当于把起始节点给遍历了 , 图没有环
     */
    public void createMinPath(String begin, Map<String, Integer> minPath, Set<String> alreadyFind, Map<String, String> parentNode, Map<String, Node> chart) {
        chart.forEach((v1, v2) -> { // v1 -> node.key ,v2 -> node
            if (v1.equals(begin)) { // v1 == begin 表示起点可以直接到达 v.key 点
                v2.value.forEach((t1, t2) -> {
                    minPath.put(t1, t2);
                    parentNode.put(t1, begin);
                });
            } else if (!minPath.containsKey(v1)) {
                minPath.put(v1, Integer.MAX_VALUE);
                parentNode.put(v1, begin);
            }
        });
        alreadyFind.add(begin);
    }

    /**
     * 找到当前最小的边
     */
    public String findMin(Set<String> alreadyFind, Map<String, Node> chart) {
        int min = Integer.MAX_VALUE;
        Set<Map.Entry<String, Node>> chartMap = chart.entrySet(); // chart 的 map
        for (Map.Entry<String, Node> chartMapEntry : chartMap) {
            Node value = chartMapEntry.getValue();
            Set<Map.Entry<String, Integer>> nodeMap = value.value.entrySet(); // node 的 map
            for (Map.Entry<String, Integer> nodeMapEntry : nodeMap) {
                if (nodeMapEntry.getValue() < min && !alreadyFind.contains(nodeMapEntry.getKey()))
                    return nodeMapEntry.getKey();
            }
        }
        return null;
    }

    public String getMin(Map<String, Node> chart, Set<String> alreadyFind, Map<String, Integer> minPath, Map<String, String> parentNode, String end) {
        while (alreadyFind.size() != chart.size() - 1) {
            Node node = chart.get(findMin(alreadyFind, chart));
            alreadyFind.add(node.key);
            node.value.forEach((v1, v2) -> { // v1 -> 连接节点的名称 , v2 -> 到连接节点的距离
                int n1 = minPath.get(node.key), n2 = minPath.get(v1);
                if (n1 + v2 < n2) {
                    minPath.put(v1, n1 + v2);
                    parentNode.put(v1, node.key);
                }
            });
        }
        StringBuilder path = new StringBuilder(end);
        ListIterator<Map.Entry<String, String>> it = new ArrayList<>(parentNode.entrySet()).listIterator(parentNode.size());
        while (it.hasPrevious()) {
            Map.Entry<String, String> previous = it.previous();
            if ((path.charAt(path.length() - 1) + "").equals(previous.getKey())) path.append(previous.getValue());
        }
        return path.reverse().toString();
    }

    private static class Node {
        String key;
        Map<String, Integer> value = new HashMap<>();

        public Node(String key, List<String> keys, List<Integer> values) {
            this.key = key;
            if (null != keys) {
                for (int i = 0; i < keys.size(); i++) this.value.put(keys.get(i), values.get(i));
            }
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key='" + key + '\'' +
                    ", value=" + value +
                    '}';
        }
    }

    public static void getMinDis(int vertex, AbstractGraph graph) {
        int[][] dijkstra = dijkstra(vertex, graph);
        int[] path = dijkstra[0];
        int[] dist = dijkstra[1];
        System.out.println("path: " + Arrays.toString(path));
        System.out.println("minDist: " + Arrays.toString(dist));
    }

    private static int[][] dijkstra(int vertex, AbstractGraph graph) {
        int n = graph.getV();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        int[] path = new int[n];
        Arrays.fill(path, -1);
        boolean[] visited = new boolean[n];
        visited[vertex] = true;
        dist[vertex] = 0;
        for (Edge edge : graph.getNeighborEdge(vertex)) {
            dist[edge.getArcHead()] = edge.getWeigh();
            path[edge.getArcHead()] = vertex;
        }
        for (int k = 1; k < n; k++) {
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++)
                if (dist[i] < min && !visited[i]) {
                    vertex = i;
                    min = dist[i];
                }
            visited[vertex] = true;
            for (Edge edge : graph.getNeighborEdge(vertex)) {
                if (!visited[edge.getArcHead()]) {
                    int dis = dist[vertex] + edge.getWeigh();
                    if (dis < dist[edge.getArcHead()]) {
                        dist[edge.getArcHead()] = dis;
                        path[edge.getArcHead()] = vertex;
                    }
                }
            }
        }
        int[][] res = new int[2][];
        res[0] = path;
        res[1] = dist;
        return res;
    }

    private static void dijkstra(AbstractGraph graph, int start) {
        int v = graph.getV();
        int[] minDist = new int[v];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[start] = 0;
        int[] path = new int[v];
        boolean[] isJoin = new boolean[v];
        for (int k = 0; k < v; k++) {
            int vertex = 0;
            for (int i = 0, cost = Integer.MAX_VALUE; i < v; i++)
                if (!isJoin[i] && minDist[i] < cost) {
                    vertex = i;
                    cost = minDist[i];
                }
            isJoin[vertex] = true;

            for (Edge edge : graph.getNeighborEdge(vertex)) {
                if (!isJoin[edge.getArcHead()]) {
                    int temp = minDist[vertex] + edge.getWeigh();
                    if (temp < minDist[edge.getArcHead()]) {
                        minDist[edge.getArcHead()] = temp;
                        path[edge.getArcHead()] = vertex;
                    }
                }
            }
        }

        System.out.println("path: " + Arrays.toString(path));
        System.out.println("minDist: " + Arrays.toString(minDist));
    }

}
